﻿// 2523. 范围内最接近的两个质数.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>


using namespace std;

/*
https://leetcode.cn/problems/closest-prime-numbers-in-range/description/

给你两个正整数 left 和 right ，请你找到两个整数 num1 和 num2 ，它们满足：

left <= nums1 < nums2 <= right  。
nums1 和 nums2 都是 质数 。
nums2 - nums1 是满足上述条件的质数对中的 最小值 。
请你返回正整数数组 ans = [nums1, nums2] 。如果有多个整数对满足上述条件，请你返回 nums1 最小的质数对。如果不存在符合题意的质数对，请你返回 [-1, -1] 。

如果一个整数大于 1 ，且只能被 1 和它自己整除，那么它是一个质数。



示例 1：

输入：left = 10, right = 19
输出：[11,13]
解释：10 到 19 之间的质数为 11 ，13 ，17 和 19 。
质数对的最小差值是 2 ，[11,13] 和 [17,19] 都可以得到最小差值。
由于 11 比 17 小，我们返回第一个质数对。
示例 2：

输入：left = 4, right = 6
输出：[-1,-1]
解释：给定范围内只有一个质数，所以题目条件无法被满足。


提示：

1 <= left <= right <= 106
*/

class Solution {
public:
    vector<int> closestPrimes(int left, int right) {
        vector<int> primes;
        vector<int> vis(1000010);
        for (int i = 2; i <= right;i++) {
            if (vis[i] == 1) continue;
            if (i >= left && i <= right) primes.push_back(i);
            if (i > right) break;
            for (int j = i = i; j <= right; j += i) {
                vis[j] = 1;
            }
        }
        int diff = 99999999; vector<int> ans{ -1,-1 };
        if (primes.size() < 2) return ans;
        for (int i = 0; i < primes.size()-1; i++) {
            int a = primes[i]; int b = primes[i + 1];
            if (b - a < diff) {
                diff = b - a;
                ans[0] = a; ans[1] = b;
            }
        }

        return ans;
    }
};

int main()
{
    Solution s;
    s.closestPrimes(1, 1);
}
 